package 动态规划算法;

public class coinChange322 {
    /**
     * 可以凑成总金额所需的 最少的硬币个数
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        //建立的二维矩阵
        int[][] dp = new int[coins.length + 1][amount + 1];
        // 将第一行赋值为最大的值
        for (int j = 1; j < dp[0].length; j++) {
            dp[0][j] = max;
        }
        // 这里开始的都是0
        // 开始的从1=(1,1)开始算  i表示物品
        for (int i = 1; i < dp.length; i++) {
            //表示当前
            int coin = coins[i - 1];
            // j表示容量
            for (int j = 1; j < dp[i].length; j++) {
                // 如果钱大于容量的时候 就不能装入
                if (coin > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 表示的是容量大于钱的时候 dp[i][j]=Math.min(dp[i-1][j],dp[i][j-coin])
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coin] + 1);
                }
            }
        }

        int[] lasti = dp[dp.length - 1];
        int lastElement = lasti[lasti.length - 1];

        return lastElement == max ? -1 : lastElement;
    }
}
